package com.leetcode.partition5;

/**
 * @author `RKC`
 * @date 2021/11/30 13:08
 */
public class LC400第N位数字 {

    public static int findNthDigit(int n) {
        //计算出第n位的数字有多少位，对于长度为len的数字范围[10^(len-1), 10^len - 1]，一共9*10^(len-1)个，总长度也就是len*9*10^(len-1)
        int len = 1;
        while (9 * len * Math.pow(10, len - 1) < n) {
            n -= 9 * len * Math.pow(10, len - 1);
            len++;
        }
        //当前位数最小的一位数字s=10^(len-1)，且对于目标值x必然满足 (x-s+1)*len>=n, x>=n/len-1+s
        long s = (long) Math.pow(10, len - 1);
        long x = n / len - 1 + s;
        //对 n 进行最后一次的试减（更新 n），若恰好有 n=0，说明答案为 x 的最后一位，可由 x % 10 取得；若大于 0，说明答案是 x+1 的第 n 位（十进制表示，从左往右数），
        //可由 (x + 1) / Math.pow(10, len - n) % 10 取得。
        n -= (x - s + 1) * len;
        return (int) (n == 0 ? x % 10 : (x + 1) / Math.pow(10, len - n) % 10);
    }

    public static void main(String[] args) {
        System.out.println(findNthDigit(101));
    }
}
